import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindAllAnagramsInAString {

    // 找到字符串中所有字符串异位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/

    public List<Integer> findAnagrams2(String ss, String pp) {
        List<Integer> ret=new ArrayList<>();
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();

        int[] hash1=new int[26];//统计字符p中每个字符出现的次数
        for(char ch:p) hash1[ch-'a']++;

        int[] hash2=new int[26];//统计窗口中每个字符出现的次数
        int m=p.length;
        for(int left=0,right=0,count=0;right<s.length;right++) {
            char in=s[right];
            hash2[in-'a']++;
            if(hash2[in-'a']<=hash1[in-'a']) count++;//说明这是一个有效字符
            if(right-left+1>m) {
                //判断
                char out=s[left++];
                if(hash2[out-'a']<=hash1[out-'a']) count--;
                hash2[out-'a']--;
            }
            if(count==m) ret.add(left);//更新结果
        }
        return ret;
    }

    // 自己写的~~,通过了,只是时间空间数据不太美观
    public List<Integer> findAnagrams(String s, String p) {
        // 统计p字符串中各字符的出现次数
        Map<Character,Integer> hash1=new HashMap<Character,Integer>();
        for(int i=0;i<p.length();i++) {
            char ch=p.charAt(i);
            hash1.put(ch,hash1.getOrDefault(ch,0)+1);
        }

        // 构造滑动窗口
        List<Integer> list=new ArrayList<>();
        Map<Character,Integer> hash2=new HashMap<Character,Integer>();// 滑动窗口区间的字符串的情况
        for(int left=0,right=0;right<s.length();right++) {
            char ch=s.charAt(right);
            hash2.put(ch,hash2.getOrDefault(ch,0)+1);//入窗口
            if(right-left+1==p.length()) {
                // 判断hash1和hash2的字符情况是否相等
                if(isSame(p,hash1,hash2)) {
                    list.add(left);
                }
                //出窗口
                hash2.put(s.charAt(left),hash2.get(s.charAt(left))-1);
                if(hash2.get(s.charAt(left))==0) hash2.remove(s.charAt(left));
                left++;
            }
        }
        return list;
    }
    private boolean isSame(String p,Map<Character,Integer> hash1,Map<Character,Integer> hash2) {
        return hash1.equals(hash2);
    }
}
